#pragma once
#include<assert.h>
#include<iostream>
#include<functional>
#include<vector>
using namespace std;


namespace my_priority_queue
{
   
    template <class T, class Container = vector<T>, class Compare = less<T> >
    class priority_queue
    {
    public:
        
       template <class InputIterator>
       priority_queue(InputIterator first, InputIterator last)
       {
           InputIterator it = first;
           while (it != last)
           {
               push(*it);
               ++it;
           }
       }

        priority_queue() {}
        

        bool empty() const
        {
            return _c.empty();
        }

        size_t size() const
        {
            return _c.size();
        }

        const T& top() const
        {
            return _c.front();
        }

        T& top()
        {
            return _c.front();
        }


        void push(const T& x)
        {
            _c.push_back(x);
            AdjustUp(size() - 1);
        }

        void AdjustUp(int child)
        {          
            int parent = (child - 1) / 2;

            while (child > 0)
            {
                if (_comp(_c[parent], _c[child]))
                {
                    swap(_c[parent], _c[child]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else
                    break;
            }
        }

        //void AdjustDown(int parent, int end)
        //{
        //    int child = parent * 2 + 1;
        //    //if (_comp(_c[child], _c[child + 1]))
        //    if(child + 1 <= end && _comp(_c[child], _c[child + 1]))
        //        ++child;

        //    while (child <= end)
        //    {
        //        if (_comp(_c[parent], _c[child]))
        //        {
        //            std::swap(_c[parent], _c[child]);
        //            parent = child;

        //            child = parent * 2 + 1;
        //            //if (_comp(_c[child], _c[child + 1]))
        //            if (child + 1 <= end && _comp(_c[child], _c[child + 1]))
        //                ++child;
        //        }
        //        else
        //            break;
        //    }
        //}

        void AdjustDown(int parent, int end)
        {
            int child = parent * 2 + 1;

            while (child <= end)
            {
                if (child + 1 <= end && _comp(_c[child], _c[child + 1]))
                    ++child;

                if (_comp(_c[parent], _c[child]))
                {
                    std::swap(_c[parent], _c[child]);
                    parent = child;
                    child = parent * 2 + 1;                
                }
                else
                    break;
            }
        }


        void pop()
        {
            assert(!empty());

            std::swap(_c[0], _c[size() - 1]);
            _c.pop_back();

            AdjustDown(0, size() - 1);
        }

    private:

        Container _c;
        Compare _comp;

    };
}


//#pragma once
//
//#include<vector>
//
//template<class T>
//class Less
//{
//public:
//	bool operator()(const T& x, const T& y)
//	{
//		return x < y;
//	}
//};
//
//template<class T>
//class Greater
//{
//public:
//	bool operator()(const T& x, const T& y)
//	{
//		return x > y;
//	}
//};

